﻿// 0812train01.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <unordered_map>
#include <unordered_set>
#include <algorithm>
#include <limits>
#include <map>

using namespace std;

/*
 某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
任意个充电设备组合的输出功率总和，均构成功率集合P的一个元素。
功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。

输入描述
输入为3行：
第一行：充电设备个数n
第二行：每个充电设备的输出功率
第三行：充电站最大输出功率p_max

输出描述
功率集合P的最优元素
补充说明：
1. 充电设备个数n > 0
2. 最优元素必须小于或等于充电站最大输出功率p_max

示例1
输入
3
1 2 3
5
输出
5
 */

void solve01(vector<int>&oh_vec, int target)
{
	int vec_size = oh_vec.size();

	unordered_set<int>dp_set;
	dp_set.insert(0);

	for (auto&curr_num:oh_vec)
	{
		//dyanmic_temp非常重要
		//否则下面insert了以后，dp_set新增了一个数
		//{0}变为{0,2}这时不会退出，会继续执行2+2，导致最后结果错误
		vector<int>dyanmic_temp(dp_set.begin(), dp_set.end());
		for (auto&set_num: dyanmic_temp)
		{
			int curr_sum = curr_num + set_num;
			if (curr_sum<= target)
			{
				cout << curr_sum << ' ';
				dp_set.insert(curr_sum);
			}
			
		}
	}

	int result = 0;
	for (auto&set_num: dp_set)
	{
		result = max(result, set_num);
	}
	cout << result;
	//solve01
}

void solve11(vector<int>&oh_vec, int target)
{
	//dp[i][prev_sum]的意思是，前i个数是否凑成prev_sum
	//if(dp[i-1][prev_sum])dp[i][prev_sum]=true
	//if(curr_num+p_sum<=target)dp[i][curr_sum]=true

	int vec_size = oh_vec.size();
	int dp_size = vec_size + 1;
	int target_size = target + 1;
	vector<int>target_vec(target_size, false);
	vector<vector<int>>dynamic_grid(dp_size, target_vec);

	//边界条件，前0个数能凑成0
	dynamic_grid[0][0] = true;
	

	for (int i=1; i<dp_size; i++)
	{
		for (int prev_sum=0;prev_sum<target_size;prev_sum++)
		{
			if (dynamic_grid[i-1][prev_sum])
			{
				dynamic_grid[i][prev_sum] = true;
				int curr_sum = oh_vec[i - 1] + prev_sum;
				if (curr_sum<=target)
				{
					dynamic_grid[i][curr_sum] = true;
				}
			}
		}
	}

	int result = 0;
	for (int sum=0; sum<=target; sum++)
	{
		if (dynamic_grid[dp_size-1][sum])
		{
			result = max(result, sum);
		}
	}

	cout << result;
	//solve11------
}


void solve21(vector<int>& oh_vec, int target)
{
	//target_size=target+1 oh_vec(target_size)
	//if(dp[prev_sum]) dp[num+prev_sum]=true

	int dp_size = target + 1;
	int vec_size = oh_vec.size();
	vector<bool>dynamic_vec(dp_size);

	dynamic_vec[0] = true;

	for (int i=1; i< vec_size; i++)
	{
		int curr_num = oh_vec[i-1];
		for (int prev_sum=0; prev_sum< dp_size; prev_sum++)
		{
			if (dynamic_vec[prev_sum])
			{
				int curr_sum = prev_sum + curr_num;
				dynamic_vec[curr_sum] = true;
			}
		}
	}

	int result = 0;
	for (int sum=0; sum<=target; sum++)
	{
		if (dynamic_vec[sum])
		{
			result = max(result, sum);
		}
	}
	cout << result;
	//
}


/*
 从n个数中选若干（至少1）个数求和，求所有方案中第k小的和（和相同但取法不同的视为不同方案）。
对于所有数据，1 <= k < 2^n， n个正整数每个都不超过10^9。
输入描述
第一行输入2个正整数n, k。
第二行输入这n个正整数。

输出描述
输出第k小的和。

示例1
输入
5 12
1 2 3 5 8
输出
8
前12小的和分别为: 1 2 3 3 4 5 5 6 6 7 8 8


示例2
输入
3 3
1 3 4
输出
4

 */
vector<int>GetCurrDp(map<int, int>&dp_map)
{
	vector<int>dp_vec;
	for (auto& map_item : dp_map)
	{
		dp_vec.push_back(map_item.first);
	}
	//for (auto&num: dp_vec)
	//{
	//	cout << num << ' ';
	//}
	//cout << '\n';
	return dp_vec;
	//GetCurrDp------
}

void solve02(vector<int>&oh_vec, int k)
{
	map<int, int>dp_map;
	//前i个数能凑出1次0
	dp_map[0] = 1;

	int vec_size = oh_vec.size();

	for (int i=0; i<vec_size; i++)
	{
		int curr_int = oh_vec[i];
		vector<int>curr_dp_vec = GetCurrDp(dp_map);
		for (int prev=curr_dp_vec.size()-1; prev>=0; prev--)
		{
			int prev_sum = curr_dp_vec[prev];
			int curr_sum = prev_sum + curr_int;
			int sum_count = dp_map[prev_sum];
			dp_map[curr_sum] += sum_count;
			
		}
		//cout << "-------" << endl;
	}

	//for (auto&map_item:dp_map)
	//{
	//	cout << map_item.first << ' ' << map_item.second << endl;
	//}

	vector<int>total_dp = GetCurrDp(dp_map);
	//for (auto&num:total_dp)
	//{
	//	cout << num << ' ';
	//}
	sort(total_dp.begin(), total_dp.end());
	total_dp=vector<int>(total_dp.begin() + 1, total_dp.end());

	int result = 0;
	int curr_count = 0;
	for (auto&sum:total_dp)
	{
		curr_count += dp_map[sum];
		//cout << sum << ' ';
		if (curr_count>=k)
		{
			result = sum;
			break;
		}
	}
	if (result==0)
	{
		result = total_dp[total_dp.size() - 1];
	}
	cout << result;
	//solve02------
}

/*
  某个充电站，可提供n个充电设备，每个充电设备均有对应的输出功率。
任意个充电设备组合的输出功率总和，均构成功率集合P的一个元素。
功率集合P的最优元素，表示最接近充电站最大输出功率p_max的元素。

输入描述
输入为3行：
第一行：充电设备个数n
第二行：每个充电设备的输出功率
第三行：充电站最大输出功率p_max

输出描述
功率集合P的最优元素
补充说明：
1. 充电设备个数n > 0
2. 最优元素必须小于或等于充电站最大输出功率p_max


变种练习，求不超过最大p_max有几种方式
示例1
输入
3
2 3 5
6
输出
2
 */

void solve03(vector<int>&oh_vec, int target)
{
	int target_size = target + 1;
	vector<int>dp_vec(target_size, 0);
	dp_vec[0] = 1;
	for (auto& num : oh_vec)
	{
		for (int prev = target; prev >= 0; prev--)
		{
			int curr_sum = num + prev;
			int sum_count = dp_vec[prev];
			if (curr_sum<=target)
			{
				dp_vec[curr_sum] += sum_count;
			}
			for (auto& num : dp_vec)
			{
				cout << num << ' ';
			}
			cout << '\n';
		}
	}

	int result = 0;
	for (int sum = 0; sum <= target; sum++)
	{
		if (dp_vec[sum] > 0)
		{
			result = max(result, sum);
		}
	}
	cout << dp_vec[result];
}

void solve04(vector<int>& oh_vec, int target)
{
	int target_size = target + 1;
	vector<int>dp_vec(target_size, 0);
	dp_vec[0] = 1;
	for (auto& num : oh_vec)
	{
		for (int prev=0; prev<=target; prev++)
		{
			int curr_sum = num + prev;
			int sum_count = dp_vec[prev];
			if (curr_sum <= target)
			{
				dp_vec[curr_sum] += sum_count;
			}
			for (auto& num : dp_vec)
			{
				cout << num << ' ';
			}
			cout << '\n';
		}
	}

	int result = 0;
	for (int sum = 0; sum <= target; sum++)
	{
		if (dp_vec[sum] > 0)
		{
			result = max(result, sum);
		}
	}
	cout << dp_vec[result];
}


int main()
{
	{
		vector<int>oh_vec = { 2,3,5 };
		int target = 6;
		solve04(oh_vec, target);
		return 0;
	}

	{
		//1 2 3 5 8
		//12 result 8
		//1 3 4
		//3 result 4
		//
		//24 15 90 90 32 79 89 35 81 42 15
		//1186 result 436
		//vector<int>oh_vec = { 43,96,84,96,95,57 };
		//int k = 32;
		//vector<int>oh_vec = { 1,2,3,5,8 };
		//int k = 12;

		//[0,1,2,3] [3,4,5,6]
		int vec_size, k;
		cin >> vec_size >> k;
		vector<int>oh_vec(vec_size);

		for (int i=0; i<vec_size; i++)
		{
			cin >> oh_vec[i];
		}

		solve02(oh_vec, k);

		return 0;
	}

	//2,3,10 9
	//1,2,3 5
	vector<int>oh_vec = { 2,3,10 };
	int target = 9;
	solve11(oh_vec, target);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
